%\newcommand{\graphfig}[2]{\begin{figure}[h!]\centering\includegraphics{../Graphs/#1}\caption{#2}\end{figure}}
\newcommand{\graphfig}[2]{\subfloat[#2]{\includegraphics{../Graphs/#1}}}
\section{Catalog of Stable Graphs} % (fold)
\label{sec:catalog_of_stable_graphs}
This appendix contains the complete catalog of all 3-, 4-, 5-, and 6-node graphs which are stable in our model. \textsc{ns} means that a graph is never stable using that utility function.


\subsection{3-node Graphs} % (fold)
\label{sub:3_node_graphs}
\begin{tabular}{>{\centering}m{0.15\textwidth}>{\centering}m{0.1\textwidth}>{\centering}m{0.1\textwidth}>{\centering}m{0.1\textwidth}}
\toprule
Graph & Standard & Infantile & Complex \tabularnewline \midrule
\begin{tikzpicture}
  \foreach \i in {0,...,2} {\path (90*\i:6mm) node (\i) [smallnode] {}; }
\end{tikzpicture} & $\frac{1}{2} \leq \alpha$ & $\frac{1}{2} \leq \alpha$ & $\frac{1}{2} \leq \alpha$ \tabularnewline
\midrule
\begin{tikzpicture}
  \foreach \i in {0,...,2} {\path (90*\i:6mm) node (\i) [smallnode] {}; }
  \draw (0) -- (1);
\end{tikzpicture} & \textsc{ns} & $\alpha=\frac{1}{2}$ & \textsc{ns} \tabularnewline 
\midrule
\begin{tikzpicture}
  \foreach \i in {0,...,2} {\path (90*\i:6mm) node (\i) [smallnode] {}; }
  \draw (0) -- (1) -- (2);
\end{tikzpicture} & $\frac{1}{6} \leq \alpha \leq \frac{5}{6}$ & $\frac{1}{6} \leq \alpha \leq \frac{1}{2}$ & $\frac{1}{6} \leq \alpha \leq \frac{5}{6}$ \tabularnewline 
\midrule
\begin{tikzpicture}
  \foreach \i in {0,...,2} {\path (90*\i:6mm) node (\i) [smallnode] {}; }
  \draw (0) -- (1) -- (2) -- (0);
\end{tikzpicture} & $\alpha \leq \frac{1}{6}$ & $\alpha \leq \frac{1}{6}$ & $\alpha \leq \frac{1}{6}$ \tabularnewline
\bottomrule
\end{tabular}
% subsection 3_node_graphs (end)


\subsection{4-node Graphs} % (fold)
\label{sub:4_node_graphs}
\begin{tabular}{>{\centering}m{0.2\textwidth}>{\centering}m{0.15\textwidth}>{\centering}m{0.15\textwidth}>{\centering}m{0.15\textwidth}}
\toprule
Graph & Standard & Infintile & Complex \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (3) [smallnode] {}; & \node (4) [smallnode] {}; \\
  };
\end{tikzpicture} &
$\frac{1}{2} \leq \alpha$ &
$\frac{1}{2} \leq \alpha$ &
$\frac{1}{2} \leq \alpha$ \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (3) [smallnode] {}; & \node (4) [smallnode] {}; \\
  };
  \draw (1) -- (2);
\end{tikzpicture} &
\textsc{ns} &
$\alpha = \frac{1}{2}$ &
\textsc{ns} \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (3) [smallnode] {}; & \node (4) [smallnode] {}; \\
  };
  \draw (3) -- (1) -- (2);
\end{tikzpicture} &
\textsc{ns} &
$\alpha = \frac{1}{2}$ &
\textsc{ns} \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (3) [smallnode] {}; & \node (4) [smallnode] {}; \\
  };
  \draw (3) -- (1) -- (2); \draw (1) -- (4);
\end{tikzpicture} &
$\frac{1}{6} \leq \alpha \leq \frac{7}{6}$ &
$\frac{1}{6} \leq \alpha \leq \frac{1}{2}$ &
$\frac{1}{6} \leq \alpha \leq \frac{7}{6}$ \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (4) [smallnode] {}; & \node (3) [smallnode] {}; \\
  };
  \draw (1) -- (2) -- (3) -- (4);
\end{tikzpicture} &
$\frac{5}{12} \leq \alpha \leq \frac{13}{12}$ &
$\frac{1}{4} \leq \alpha \leq \frac{1}{2}$ &
$\frac{5}{12} \leq \alpha \leq \frac{13}{12}$ \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (3) [smallnode] {}; & \node (4) [smallnode] {}; \\
  };
  \draw (4) -- (1) -- (2) -- (3) -- (1) -- (3);
\end{tikzpicture} &
$\frac{1}{12} \leq \alpha \leq \frac{1}{6}$ &
$\alpha = \frac{1}{6}$ &
$\alpha = \frac{1}{6}$ \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (4) [smallnode] {}; & \node (3) [smallnode] {}; \\
  };
  \draw (1) -- (2) -- (3) -- (4) -- (1);
\end{tikzpicture} &
$\frac{1}{4} \leq \alpha \leq \frac{5}{12}$ &
$\frac{1}{6} \leq \alpha \leq \frac{1}{4}$ &
$\frac{1}{6} \leq \alpha \leq \frac{5}{12}$ \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (3) [smallnode] {}; & \node (4) [smallnode] {}; \\
  };
  \draw (1) -- (3); \draw (1) -- (4); \draw (1) -- (2);
  \draw (2) -- (3); \draw (2) -- (4);
\end{tikzpicture} &
\textsc{ns} &
$\alpha = \frac{1}{6}$ &
$\alpha = \frac{1}{6}$ \tabularnewline \midrule
\begin{tikzpicture}
  \node [matrix,column sep=4mm,row sep=4mm] {
    \node (1) [smallnode] {}; & \node (2) [smallnode] {}; \\
    \node (3) [smallnode] {}; & \node (4) [smallnode] {}; \\
  };
  \draw (1) -- (3); \draw (1) -- (4); \draw (1) -- (2);
  \draw (2) -- (3); \draw (2) -- (4);
  \draw (3) -- (4);
\end{tikzpicture} &
$\alpha \leq \frac{1}{4}$ &
$\alpha \leq \frac{1}{6}$ &
$\alpha \leq \frac{1}{6}$ \tabularnewline
\bottomrule
\end{tabular}
% subsection 4_node_graphs (end)

\subsection{5-node Graphs} % (fold)
\label{sub:5_node_graphs}
Please see the attached hand-drawings.

\subsection{6-node Graphs} % (fold)
\label{sub:6_node_graphs}
Please see the attached hand-drawings.

% \begin{figure}[h!]
%   \graphfig{5/empty.pdf}{Empty graph}
%   \graphfig{5/star.pdf}{Star}
%   \graphfig{5/star_tail.pdf}{Star with a tail} \\
%   \graphfig{5/line.pdf}{Line}
%   \graphfig{5/bipartite.pdf}{Complete bipartite}
%   \graphfig{5/k_tail.pdf}{$K_4$ with tail} \\
%   \graphfig{5/ring.pdf}{Ring}
%   \graphfig{5/divided_ring.pdf}{Divided ring}
%   \graphfig{5/complete.pdf}{Complete}
% \end{figure}

% subsection 5_node_graphs (end)
% section catalog_of_stable_graphs (end)

\section{Single-tail Graph Stability with the Complex Utility Function} % (fold)
\label{sec:single_tail_graph_stability}
Consider the following graph of $n$ nodes where $n \geq 5$ with nodes $a$, $b$, $c$, and $d$. The stable $\alpha$ range under the complex utility function is very different from the range under the standard utility function. 
Theorem: The $\alpha$ bound for a graph (where there are at least five nodes) consisting of a clique with a single node connecting to it is $\alpha = \frac{1}{6}$ when using the complex utility function.
Proof:
First we find the utilities of some important nodes:

\[u(a) = \frac{1}{2} + \frac{n-2}{3} - \alpha~,\]
\[u(b) = \frac{n-1}{2} + \frac{n-2}{3} - (n-1)\alpha~,\]
\[u(c) = \frac{n-2}{2} + \frac{1}{3} - (n-2)\alpha~,\]
\[u(d) = \frac{n-2}{2} + \frac{1}{3} - (n-2)\alpha~.\]

If an edge is created from $a$ to $c$, the resulting utilities are:
\[u(a) = \frac{2}{2} + \frac{n-3}{3} - 2\alpha~,\]
\[u(c) = \frac{n-1}{2} + \frac{n-3}{6} - (n-1)\alpha~.\]
So $a$ will not form the edge whenever $\alpha \geq \frac{1}{6}$ and $c$ will not form the edge whenever $\alpha \geq \frac{1}{2} + \frac{n-5}{6}$. Since both have to benefit for the edge to form (and $n \geq 5$), the edge will not form when $\alpha \geq \frac{1}{6}$. Note that all other edge additions result in isomorphic graphs so $\frac{1}{6}$ is the infimum of $\alpha$ for stability.

If the edge from $c$ to $d$ is dropped then the utilities are:
\[u(c) = \frac{n-3}{2} + \frac{2}{3} - (n-3)\alpha~,\]
\[u(d) = \frac{n-3}{2} + \frac{2}{3} - (n-3)\alpha~.\]
So this edge will be kept when:
\[\alpha \leq \frac{1}{6} ~.\]

The other possible moves that result in non-isomorphic graphs are: dropping the edge from $a$ to $b$ and dropping the edge from $b$ to $c$. It can be easily shown that these edges will remain for $\alpha \leq \frac{1}{6}$. Therefore a singled-tailed complete graph is stable only when $\alpha = \frac{1}{6}~.$
% section single_tail_graph_stability (end)
